package com.leetcode.algorithm.topic;

/**
 * 位运算相关算法题解
 * 136. 只出现一次的数字
 * 190. 颠倒二进制位
 * 461. 汉明距离
 * 371. 两整数之和
 * 405. 数字转换为十六进制数
 * @author: jie.deng
 * @time: 2018年6月2日 下午5:30:53
 */
public class BitSolution {
	
	/**
	 * 136. 只出现一次的数字 
	 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
	 * 
	 * 说明：
	 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
	 * 
	 * 示例 1:
	 * 输入: [2,2,1] 
	 * 输出: 1 
	 * 
	 * 示例 2:
	 * 输入: [4,1,2,1,2] 
	 * 输出: 4
	 * 
	 * @param nums
	 * @return
	 */
	public int singleNumber(int[] nums) {
		int number = 0;
		for (int i = 0; i < nums.length; i++) {
			number ^= nums[i];	// 异或运算找出只出现一次的数字
		}
		return number;
	}
	
    /**
	 * 190. 颠倒二进制位 
	 * 颠倒给定的 32 位无符号整数的二进制位。
	 * 
	 * 示例:
	 * 输入: 43261596 
	 * 输出: 964176192 
	 * 解释: 43261596 的二进制表示形式为  00000010100101000001111010011100 ， 
	 * 返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。 
	 * 
	 * 进阶: 
	 * 如果多次调用这个函数，你将如何优化你的算法？
	 * 
	 * @param n
	 * @return
	 */
	public int reverseBits(int n) {
		int result = 0;
		for (int i = 0; i < 32; i++) {
			result = result << 1;
			result ^= (n & 1);	//n & 1获取n的最后一位
			n = n >>> 1;
		}
		return result;
	}
	
	/**
	 * 461. 汉明距离
	 *	两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
	 *	给出两个整数 x 和 y，计算它们之间的汉明距离。
	 *
	 *	注意：
	 *	0 ≤ x, y < 2的31次方.
	 *	示例:
	 *	输入: x = 1, y = 4
	 *	输出: 2
	 *	解释:
	 *	1   (0 0 0 1)
	 *	4   (0 1 0 0)
	 *	       ↑   ↑
	 *	上面的箭头指出了对应二进制位不同的位置。
	 * @param x
	 * @param y
	 * @return
	 */
	public int hammingDistance(int x, int y) {
		int hamming = x ^ y; // 异或运算(同0异1)
		int cnt = 0;
		while (hamming > 0) {
			hamming = hamming & (hamming - 1); // 很奇妙地计算出hamming的二进制表示中1的个数
			cnt++;
		}
		return cnt;
	}

	/**
	 * 371. 两整数之和
	 * 
	 * 不使用运算符 + 和-，计算两整数a 、b之和。
	 * 示例： 若 a = 1 ，b = 2，返回 3。
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public int getSum(int a, int b) {
		int sum = a ^ b; // 半加器
		int carry = ((a & b) << 1); // 进位
		if (carry == 0) {
			return sum;
		} else {
			return getSum(sum, carry);
		}
	}
	
	/**
	 * 405. 数字转换为十六进制数
	 * 给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
	 * 
	 * 注意:
	 * 十六进制中所有字母(a-f)都必须是小写。
	 * 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
	 * 给定的数确保在32位有符号整数范围内。 
	 * 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。 
	 * 
	 * 示例 1：
	 * 输入: 26
	 * 输出: "1a" 
	 * 
	 * 示例 2：
	 * 输入: -1
	 * 输出: "ffffffff"
	 * 
	 * @param num
	 * @return
	 */
	public String toHexSolution(int num) {
		if (num == 0) {
			return "0";
		}
		char[] chars = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
		StringBuffer sb = new StringBuffer();
		while (num != 0) {
			sb.append(chars[num & 0xf]);	// num & 0xf 获取二进制表示的后4位
			num >>>= 4;
		}
		return sb.reverse().toString();
	}
}